//
// Created by ASUS on 2024/12/14/星期六.
//
const int MX = 100000;
int phi[MX + 1];
void sievePhi() {
	for (int i = 0; i <= MX; i++) {
		phi[i] = i;
	}
	for (int p = 2; p <= MX; p++) {
		if (phi[p]==p) {
			// p是质数
			for (int k = p; k <= MX; k += p) {
				phi[k]-=phi[k]/p;
			}
		}
	}
}
//1——n中与n互质的个数
int Euler(int n) {
	int cnt=n;
	for(int i=2;i*i<=n;i++){
		if(n%i)continue;
		while(n%i==0){
			n=n/i;
		}
		cnt=cnt/i*(i-1);
	}
	if(n>1)cnt=cnt/n*(n-1);
	return cnt;
}
/*
 * 已知Euler(a)=m,则Euler(a^b)=m*(a^(b-1))
 */